/*
 * @lc app=leetcode.cn id=92 lang=java
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 解法1：
        // ListNode dummy=new ListNode(0);
        // dummy.next=head;
        // ListNode prev=dummy;
        // while(m>1){
        //     prev=prev.next;
        //     m--;
        //     n--;
        // }
        // head=prev.next;

        // while(n>1){
        //     ListNode next=head.next;

        //     head.next=head.next.next;
        //     next.next=prev.next;
        //     prev.next=next;
        //     n--;
        // }
        // return dummy.next;

        // 解法2：
        if (m == 1) {
            return reverseN(head, n);
        }
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    ListNode successor = null;

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}
// @lc code=end
